package ljl.alg.jianzhioffer.round3.medium;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 一个隐藏的优化：只需要往右、往下搜索，不用往左、上搜索
 * */
public class _13_movingCount {

    /**
     * 一般来说递归都是最快的！
     * */
    class lufei_dfs {
        int m, n, k;
        boolean[][] visited;
        public int movingCount(int m, int n, int k) {
            this.m = m; this.n = n; this.k = k;
            this.visited = new boolean[m][n];
            return dfs(0, 0, 0, 0);
        }
        public int dfs(int i, int j, int si, int sj) {
            if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
            visited[i][j] = true;
            return dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj)
                    + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8)
                    + 1;
        }
    }

    /**
     * 这个解法非常的慢
     * */
    class lufei_bfs {
        public int movingCount(int m, int n, int k) {
            boolean[][] visited = new boolean[m][n];
            int res = 0;
            Queue<int[]> queue= new LinkedList<>();
            queue.add(new int[] { 0, 0, 0, 0 });
            while(queue.size() > 0) {
                int[] x = queue.poll();
                int i = x[0], j = x[1], si = x[2], sj = x[3];
                if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
                visited[i][j] = true;
                res ++;
                queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
                queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
            }
            return res;
        }

    }

    /**
     * 这个解法比较慢
     * */
    class official_iterate {
        public int movingCount(int m, int n, int k) {
            if (k == 0) return 1;
            boolean[][] visited = new boolean[m][n];
            int res = 1;
            visited[0][0] = true;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0 || get(i) + get(j) > k)
                        continue;
                    if (i > 0)
                        visited[i][j] |= visited[i - 1][j];
                    if (j > 0)
                        visited[i][j] |= visited[i][j - 1];
                    if (visited[i][j])
                        res++;
                }
            }
            return res;
        }

        private int get(int x) {
            int res = 0;
            while (x != 0) {
                res += x % 10;
                x /= 10;
            }
            return res;
        }
    }
}
